#include"configure/switch.hpp"

#if xuse_gc
#ifndef xpack_gc_private_gc_background
#define xpack_gc_private_gc_background
#pragma push_macro("xuser")
#undef  xuser
#define xuser mixc::gc_private_gc_background::inc
#include"define/base_type.hpp"
#include"concurrency/lock/atom_fetch_add.hpp"
#include"concurrency/lock/atom_add.hpp"
#include"concurrency/lock/atom_load.hpp"
#include"concurrency/lock/atom_store.hpp"
#include"concurrency/lock/atom_sub.hpp"
#include"concurrency/lock/atom_swap.hpp"
#include"concurrency/lock/cache_load.hpp"
#include"concurrency/lock/cache_store.hpp"
#include"concurrency/thread.hpp"
#include"concurrency/thread_self.hpp"
#include"configure/limit.hpp"
#include"gc/private/gc_token.hpp"
#include"gc/private/gc_performance_counter.hpp"
#include"macro/xcheck_binary_aligned.hpp"
#include"macro/xdefer.hpp"
#include"macro/xexport.hpp"
#include"macro/xinit.hpp"
#include"macro/xthread_local.hpp"
#include"macro/xmodify.hpp"
#include"utils/memory.hpp"
#pragma pop_macro("xuser")

namespace mixc::gc_private_gc_background::origin{
    using release_invoke        = void(*)(voidp mem);

    struct release_pair{
        inc::gc_token<true/*with_gc*/> *    mem;
        release_invoke                      release;
    };

    constexpr uxx gc_filter_queue_depth_mask    = inc::limit::max_gc_filter_queue_depth - 1;
    constexpr uxx gc_free_list_queue_depth_mask = inc::limit::max_gc_free_list_queue_depth - 1;
    xcheck_binary_aligned(inc::limit::max_gc_filter_queue_depth);
    xcheck_binary_aligned(inc::limit::max_gc_free_list_queue_depth);

    using free_nodep            = inc::gc_token<true/*with gc*/>::free_nodep;
    using release_pairp         = release_pair *;

    // 控制 g_gc_filter_thread 中的[内析构]不再推送给自己，而是直接执行
    // 该值只会在 g_gc_filter_thread 中设置，其他线程读到的都是 false
    xthread_local(l_in_release,  bool);
    xthread_local(l_wait_mem,  voidp);
    xthread_local(l_i_wait,  uxx);

#if xuse_gc_performance_counter
    xthread_local(l_pc, inc::gc_performance_counter);
#endif

    // 等待 GC 同步的线程数
    inline uxx                  g_pending;

    // gc 对象筛选队列
    inline release_pair         gc_filter_queue[inc::limit::max_gc_filter_queue_depth];

    // gc 释放列表
    inline free_nodep           g_free_list;

    // 存放索引，当前推送的内容存放到 gc_filter_queue 的哪一个元素中
    inline uxx                  g_i_push_gc_que;

    // 取出索引，gc_thread 处理了多少 gc_filter_queue 中的请求
    inline uxx                  g_i_pop_gc_que;


#if xuse_gc_releaser
    // g_gc_filter_thread 和 g_gc_releaser_thread 通过此字段进行交互，这是一个生产者消费者模型。
    // g_gc_filter_thread 负责将 push 到 gc 的对象筛选出需要释放的对象，
    // 每一轮筛选会按顺序依次占用一个 g_free_list_queue 中的元素，用于存放带释放的内存链表
    // g_gc_releaser_thread 负责从 g_free_list_queue 取元素，并将取出元素的位置设置为 nullptr，
    // 表示这个位置空闲
    inline free_nodep           g_free_list_queue[inc::limit::max_gc_free_list_queue_depth];
    inline uxx                  g_gc_releaser_exit;
    inline inc::thread          g_gc_releaser_thread;
#endif

    inline uxx                  g_gc_filter_exit;
    inline inc::thread          g_gc_filter_thread;

    // 注意：###############################################################
    // g_gc_filter_thread、g_gc_releaser_thread 应该在此 xdefer_global 的前面，
    // 以确保在执行此 xdefer_global 时它们没有析构
    // gc 退出触发器，当全局析构时触发
    xdefer_global{
        for(inc::atom_store(xmodify(g_gc_filter_exit), true);
            inc::atom_load(xmodify(g_gc_filter_exit));
            inc::thread_self::yield()){
        }
    };

    inline void gc_filter(){
        for(auto i_queue = 0; inc::atom_load(xmodify(g_gc_filter_exit)) == false;){
            auto i_push         = inc::atom_load(xmodify(g_i_push_gc_que));
            auto i_pop          = g_i_pop_gc_que;
            auto dis            = i_push - g_i_pop_gc_que;

            if (dis >= inc::limit::max_gc_filter_queue_depth) {
                i_push          = g_i_pop_gc_que + inc::limit::max_gc_filter_queue_depth;
            }

            if (dis == 0){
                inc::thread_self::suspend(64/*ms*/);
                continue;
            }

            // 等待超时就响应一下
            if (inc::atom_load(xmodify(g_pending)) == 0 and dis < inc::limit::max_gc_queue_threshold){
                inc::thread_self::suspend(64/*ms*/);
            }

            using tp            = inc::gc_token<true/* with gc */> *;
            using rpp           = release_pair *;
            auto i_begin        = i_pop;
            auto i_end          = i_push;
            auto i              = i_pop;
            auto release        = release_invoke{};
            auto mem            = tp{};
            auto item           = rpp{};

            // 去除重复的析构（mem 指向的值一样）
            // 相同指向的 mem 只保留最后的一个，保证释放的顺序，所以循环是从后往前
            // 批量让引用计数器减一

            // 注意：
            // 如果是 gc 中筛选已经无有效引用的对象，可以析构，但需要推迟释放内存（等到本轮 gc 结束）
            // 由于 [内部引用计数步骤] 会改变引用计数器，假如判定当前对象无有效引用，我们释放了该对象指向的内存，
            // 而 gc 队列中可能还存在和当前对象相同指向的任务，那么在队列中取出 A 任务时将会对内存非法访问
            // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
            // 在 gc 筛选步骤，也是可能变对象的引用计数器的，不要假定只有这块代码会改变引用计数

            // 从前往后找，直到遇到 item->mem == nullptr
            for(inc::cache_load(); i != i_end; i++){
                if (item = xmodify(gc_filter_queue[i & gc_filter_queue_depth_mask]); item->mem == nullptr){
                    i_end       = i;
                    break;
                }
            }

            // 从后往前去重，这样可以保证析构顺序
            while(i != i_begin){
                i              -= 1;
                item            = xmodify(gc_filter_queue[i & gc_filter_queue_depth_mask]);
                mem             = item->mem;

                // mem 为 nullptr 指示当前元素在对应的线程中还未完成设置
                if (mem->owners_decrease(); mem->in_gc_queue()){
                    item->mem   = nullptr;
                }
                else{
                    mem->in_gc_queue(true);
                }
            }

        #if xuse_gc_releaser
            // 可能是来自 push 达到阈值 xgc_queue_threshold 时唤醒
            // 所以被唤醒时，仍以当前队列是否空闲作为标志
            while(true){
                if (g_free_list = inc::atom_load(xmodify(g_free_list_queue[i_queue])); 
                    g_free_list == nullptr){
                    break;
                }
                inc::thread_self::suspend(64);
            }
        #else
            (void)i_queue;
        #endif

            // gc 筛选
            for(inc::gc_token<true/* with gc */>::new_term(); i != i_end;) {
                item            = xmodify(gc_filter_queue[i & gc_filter_queue_depth_mask]);
                i              += 1;
                i_pop          += 1;
                release         = item->release;
                mem             = item->mem;

                // 不执行重复无效的遍历
                // 只有该节点是在本轮 gc 中第一次访问，才可以进行接下来的[外析构]
                if (mem and not mem->is_visited() and not mem->under_release()){
                    release(mem); // 如果该对象可以释放，则会将要释放的内存添加到 g_free_list 链表中
                }

                // 该对象可能在 gc 遍历其他对象时已经经过了
                // 所以我们不能将 mem->in_gc_queue(false) 放到 release(mem) 后边，而是单独作为一个 if
                // 对于该对象仍活跃的情况我们必须复位 in_gc_queue 以便一下次送入 gc 队列时不被误判
                if (mem){
                    mem->in_gc_queue(false);
                }

                // 需要先置空，再设置 g_i_pop_gc_que
                // 只有下一次读到 mem 值不为 nullptr 时才响应
                inc::atom_store(xmodify(item->mem), nullptr);

                // 让 gc_filter_queue 立即腾出可用的空间
                inc::atom_store(xmodify(g_i_pop_gc_que), i_pop);
            }

            // 注意：
            // 如果是 gc 中筛选已经无有效引用的对象，可以析构，但需要推迟释放内存（等到本轮 gc 结束）
            // 由于 [内部引用计数步骤] 会改变引用计数器，假如判定当前对象无有效引用，我们释放了该对象指向的内存，
            // 而 gc 队列中可能还存在和当前对象相同指向的任务，那么在队列中取出 A 任务时将会对内存非法访问
            // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        #if xuse_gc_releaser
            if (g_free_list){
                inc::cache_store();
                inc::atom_store(xmodify(g_free_list_queue[i_queue]), g_free_list);
                i_queue        += 1;
                i_queue        &= gc_free_list_queue_depth_mask;
                g_gc_releaser_thread.resume();
            }
        #else
            while(g_free_list != nullptr){
                auto current    = g_free_list;
                auto bytes      = inc::memory::size{(*current)->bytes};
                g_free_list     = (*g_free_list)->prev;
                inc::memory::free(current, bytes);
            }
        #endif
        }

    #if xuse_gc_releaser
        // 先设置标志量，再唤醒 releaser
        for(inc::atom_store(xmodify(g_gc_releaser_exit), true), g_gc_releaser_thread.resume();
            inc::atom_load(xmodify(g_gc_releaser_exit));
            inc::thread_self::yield()){
        }
    #endif

        // 回应 xdefer_global，表示操作已经完成
        inc::atom_store(xmodify(g_gc_filter_exit), false);
    }

#if xuse_gc_releaser
    inline void gc_releaser(){
        for(uxx i_queue = 0;;){
            auto free_list      = free_nodep{};
            auto current        = free_nodep{};
            auto bytes          = inc::memory::size{0};

            // 如果遇到退出标志，可以立即退出，因为纯内存释放操作可以不用在系统退出时执行
            // 由于 suspend 只会让挂起信号量 -1，而 filter 线程可以多次调用 resume 让信号量多次 +1
            if (free_list = inc::atom_load(xmodify(g_free_list_queue[i_queue])); free_list){
                ;
            }
            else if (inc::thread_self::suspend(); inc::atom_load(xmodify(g_gc_releaser_exit))){
                break;
            }

            if (free_list = inc::atom_swap<free_nodep>(xmodify(g_free_list_queue[i_queue]), nullptr); free_list == nullptr){
                continue;
            }

            inc::cache_load();
            g_gc_filter_thread.resume();
            i_queue            += 1;
            i_queue            &= gc_free_list_queue_depth_mask;

            // 然后做释放内存等耗时操作
            while(free_list != nullptr){
                current         = free_list;
                free_list       = (*free_list)->prev;
                bytes           = inc::memory::size{(*current)->bytes};
                inc::memory::free(current, bytes);
            }
        }

        // 回应一下 filter 线程
        inc::atom_store(xmodify(g_gc_releaser_exit), false);
    }
#endif

    inline void gc_sync(){
        if (*l_wait_mem == nullptr){
            return;
        }

        inc::atom_add(xmodify(g_pending), 1);
        g_gc_filter_thread.resume();

        // 如果 gc 还未处理完该 mem 就自旋等待
        while(inc::atom_load(xmodify(gc_filter_queue[*l_i_wait].mem)) == *l_wait_mem){
            inc::thread_self::yield();
        }
        inc::atom_sub(xmodify(g_pending), 1);
    }

    // 注意：mem 不能为 nullptr
    inline void gc_push(inc::gc_token<true/* with gc */> * mem, release_invoke release){
        uxx i_push              = inc::atom_fetch_add(xmodify(g_i_push_gc_que), 1);
        uxx i_pop               = 0;
        uxx i                   = 0;
        uxx dis                 = 0;
        uxx sleep_count         = 0;
        uxx yield_count         = 0;

        for(uxx counter = 0;; counter++){
            i_pop               = inc::atom_load(xmodify(g_i_pop_gc_que));
            i                   = i_push & gc_filter_queue_depth_mask;
            dis                 = i_push - i_pop;

            if (dis < inc::limit::max_gc_filter_queue_depth){
                break;
            }

            if ((counter & 0xf) == 0xf){
                sleep_count    += 1;
                inc::thread_self::sleep(1);
            }
            else{
                yield_count    += 1;
                inc::thread_self::yield();
            }
        }

    #if xuse_gc_performance_counter
        if (l_pc->exec_times += 1; sleep_count){
            l_pc->sleep_times  += 1;
            l_pc->sleep_ms     += sleep_count;

            if (l_pc->max_sleep < sleep_count){
                l_pc->max_sleep = sleep_count;
            }
        }

        if (yield_count){
            if (l_pc->yield_times += yield_count; l_pc->max_yield < yield_count){
                l_pc->max_yield = yield_count;
            }
        }
    #else
        (void)sleep_count;
        (void)yield_count;
    #endif

        // 设置当前等待 gc 完成的元素
        *l_i_wait               = i;
        *l_wait_mem             = mem;

        // 后设置 mem，该字段不为 nullptr 指示当前元素设置完成
        inc::atom_store(xmodify(gc_filter_queue[i].release), release);
        inc::atom_store(xmodify(gc_filter_queue[i].mem), mem);

        if (i == inc::limit::max_gc_queue_threshold){
            g_gc_filter_thread.resume();
        }
    }

    xinit(inc::the_gc_background){
        g_gc_filter_thread      = inc::thread(xdetached{
            gc_filter();
        });

    #if xuse_gc_releaser
        g_gc_releaser_thread    = inc::thread(xdetached{
            gc_releaser();
        });
    #endif
    };
}

#endif

xexport_space(mixc::gc_private_gc_background::origin)

#endif
